import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    //最长湍流子数组
    public int maxTurbulenceSize(int[] nums) {
        int n = nums.length;
        //f[i]表示第i个位置呈上升最长湍流子数组
        int[] f = new int[n];
        //g[i]表示第i个位置呈下降最长湍流子数组
        int[] g = new int[n];
        for(int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        int max = 1;
        for(int i = 1; i < n; i++) {
            if(nums[i] < nums[i-1]) {
                g[i] = f[i-1] +1;
                if(max < g[i]) {
                    max = g[i];
                }
            }
            if(nums[i] > nums[i-1]) {
                f[i] = g[i-1] +1;
                if(max < f[i]) {
                    max = f[i];
                }
            }
        }
        return max;
    }
    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash = new HashSet(wordDict);
        int n = s.length();
        //dp[i]表示[0-i]范围内能否被字典中的单词拼接而成
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        s = " "+s;
        for(int i = 1; i <= n; i++) {
            for(int j = i; j >= 1; j--) {
                if(dp[j-1]  && hash.contains(s.substring(j,i+1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}
